package dataStructures;

// generic binary search tree

public class BinarySearchTree<T extends Comparable<? super T>> {
	
	private Node<T> root;
	
	public BinarySearchTree(T rootValue){
		root = new Node<T>(rootValue,null,null,null);
	}
	
	public void insertNode(T nodeValue){
		Node<T> correctParent = root;
		Node<T> newNode = new Node<T>(nodeValue,null,null,null);
		while(correctParent!=null){
			if(newNode.compareTo(correctParent)<0){
				if(correctParent.getLeftNode()==null){
					correctParent.setLeftNode(newNode);
					newNode.setParent(correctParent);
					break;
				}else{
					correctParent = correctParent.getLeftNode();
					continue;
				}
			}else if(newNode.compareTo(correctParent)>0){
				if(correctParent.getRightNode()==null){
					correctParent.setRightNode(newNode);
					newNode.setParent(correctParent);
					break;
				}else{
					correctParent = correctParent.getRightNode();
					continue;
				}
			}else{
				System.out.println("Element already in Tree");
			}
		}	
	}
	
	public Node<T> isPresent(T nodeValue){
		boolean result = false;
		Node<T> currentNode = root;
		
		while(currentNode!=null){
			
			int compVal = nodeValue.compareTo(currentNode.getValue()); 
			
			if(compVal == 0){
				result = true;
				break;
			}
			else if(compVal<0){
				currentNode = currentNode.getLeftNode();
			}else if(compVal > 0){
				currentNode = currentNode.getRightNode();
			}
		}
		
		if(result == true){
			return currentNode;
		}
		return null;
	}

    public void deleteNode(T value){
        Node<T> rootNode = isPresent(value);
        deleteNode(rootNode);
    }
	
	private void deleteNode(Node<T> rootNode){
		if(rootNode==null) {
			System.out.println("Nothing to delete. Item not present");
			return;
		}
		Node<T> parent = rootNode.getParent();
		boolean leftChild = false;
		if(parent!=null){
		 leftChild = rootNode.compareTo(rootNode.getParent()) < 0;
		}
		if(rootNode.getLeftNode() == null && rootNode.getRightNode() == null){
			// its a leaf, just delete it 
			
			rootNode.setParent(null);
			if(parent!=null){
				if(leftChild){
					// leftNode
					parent.setLeftNode(null);
				}else{
					parent.setRightNode(null);
				}
			}
		}
		else if(rootNode.getLeftNode()==null){
			// replace its rightNode with itself
			Node<T> rightNode = rootNode.getRightNode();
			if(parent!=null){
				if(leftChild) parent.setLeftNode(rightNode);
				else parent.setRightNode(rightNode);
				rightNode.setParent(parent);
			}
		}else if(rootNode.getRightNode()==null){
			Node<T> leftNode = rootNode.getLeftNode();
			if(parent!=null){
				if(leftChild) parent.setLeftNode(leftNode);
				else parent.setRightNode(leftNode);
				leftNode.setParent(parent);
			}
		}else{
			// the real part
			// find in-order successor and replace
			// guaranteed to have only 0 or 1 child
            Node<T> successor = getInOrderSuccessor(rootNode);
			T value = successor.getValue();

            deleteNode(successor);
            rootNode.setValue(value);

		}
	}
	
	public void inOrderTraverse(){
		inOrderTraverse(root);
	}
	
	private void inOrderTraverse(Node<T> rootNode){
		
		if(rootNode.getLeftNode() == null && rootNode.getRightNode() == null){
			System.out.print(rootNode.getValue()+" ");
			return;
		}
		if(rootNode.getLeftNode() != null) inOrderTraverse(rootNode.getLeftNode());
		System.out.print(rootNode.getValue()+" ");
		if(rootNode.getRightNode() != null) inOrderTraverse(rootNode.getRightNode());
		
	}
	
	private Node<T> getInOrderSuccessor(Node<T> rootNode){
		// find the leftmost child of the rightSubtree
		Node<T> rightTree = rootNode.getRightNode();
		while(rightTree.getLeftNode()!=null){
			rightTree = rightTree.getLeftNode();
		}
		return rightTree;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>(10);
		
		tree.insertNode(5);
		tree.insertNode(15);

        tree.deleteNode(10);
        tree.inOrderTraverse();
        System.out.println("\n10 gone \n");


        tree.insertNode(1);
		tree.inOrderTraverse();
		System.out.println("\n");
		tree.insertNode(12);
		tree.insertNode(4);
		tree.inOrderTraverse();
		System.out.println("\n");
		tree.insertNode(8);
		
		tree.insertNode(20);
		
		tree.inOrderTraverse();
		System.out.println("\n");
		
		tree.deleteNode(4);
		tree.inOrderTraverse();
		System.out.println("\n4 gone \n");
		
		tree.deleteNode(1);
		tree.inOrderTraverse();
		System.out.println("\n1 gone \n");
		
		tree.deleteNode(10);
		tree.inOrderTraverse();
		System.out.println("\n10 gone \n");

        tree.insertNode(10);
        tree.inOrderTraverse();
        System.out.println("\n10 back \n");
    }
	
	
	class Node<T extends Comparable<? super T>> implements Comparable{
		T value;
		Node<T> leftNode;
		Node<T> rightNode;
		Node<T> parent;
		
		public Node(T value1, Node<T> leftNode, Node<T> rightNode, Node<T> parent){
			this.value = value1;
			this.leftNode = leftNode;
			this.rightNode = rightNode;
			this.parent = parent;
		}
		
		public void setLeftNode(Node<T> leftNode){
			this.leftNode = leftNode;
		}
		
		public void setRightNode(Node<T> rightNode){
			this.rightNode = rightNode;
		}
		
		public void setParent(Node<T> parent){
			this.parent = parent;
		}
		
		public T getValue(){
			return value;
		}

        public void setValue(T value){
            this.value = value;
        }
		
		public Node<T> getLeftNode(){
			return leftNode;
		}
		
		public Node<T> getRightNode(){
			return rightNode;
		}
		
		public Node<T> getParent(){
			return parent;
		}

		@Override
		public int compareTo(Object arg0) {
			Node<T> temp = (Node<T>) arg0;
			return value.compareTo(temp.getValue());
		}
		
		@Override
		public boolean equals(Object o){
			return value == ((Node<T>) o).getValue();	
		}
		
	}

}
